package stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author dx
 * @version 1.0
 * @date 2022/3/27 11:11
 * @description:  设计一个支持push,pop,top操作，并能在常数时间内检索到最小元素的栈：
 * 实现MinStack类：
 * Minstack() 初始化堆栈对象
 * void push(int val)   将元素val推入堆栈
 * void pop() 删除堆栈顶部的元素
 *
 *
 * 基本思路：采用两个栈，一个栈正常push和pull,另外一个栈每次push的时候比较当前栈顶和要push元素的大小，保证栈顶始终每次Push的都是最小值
 */
public class Minstack {

    Deque<Integer> stack = null;
    Deque<Integer> min = null;

    public Minstack(){

        stack = new LinkedList<Integer>();
        min = new LinkedList<Integer>();
        min.push(Integer.MIN_VALUE);
    }
    public void push(int val){
        stack.push(val);
        min.push(Math.min(min.peek(),val));
    }
    public void pop(){
        stack.pop();
        min.pop();
    }
    public int getMin(){
        return min.peek();
    }
    public int top(){
        return stack.peek();
    }
}
